package leetcode.周赛.双周赛.第67场;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/12 0:41
 * @description：
 */
public class 引爆最多的炸弹 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.maximumDetonation(new int[][]{{1,1,100000},{100000,100000,1}}));
    }

    class Solution {
        public int maximumDetonation(int[][] bombs) {
            int max = 0;
            int idx = 0;
            for (int[] bomb : bombs) {
                boolean[] isBump = new boolean[bombs.length];
                isBump[idx] = true;
                max = Math.max(max, dfs(bombs, isBump, idx, 1));
                idx++;
            }
            return max;
        }

        private int dfs(int[][] bombs, boolean[] isBump, int idx, int sum) {
            int x = bombs[idx][0];
            int y = bombs[idx][1];
            int r = bombs[idx][2];
            for (int i = 0; i < bombs.length; i++) {
                if (isBump[i]) continue;
                int[] bomb = bombs[i];
                if (Math.sqrt((x - bomb[0]) * (x - bomb[0]) + (y - bomb[1]) * (y - bomb[1])) <= (r + bomb[2])) {
                    isBump[i] = true;
                    sum += dfs(bombs, isBump, i, 1);
                }
            }
            return sum;
        }
    }

}
